class Solution {
    /*
    思路：
        对于序列【2, 6, 3, 5, 4, 1】,我们需要找到它的下一个排列，可以从后往前看，
        对于【4,1】已经是最大的排列了
        对于【5，4，1】已经是最大的排列了
        对于【3,5,4,1】我们可以发现这个序列不是最大的，所以我们可以通过重新组合这个排列来
        找到下一个排列，由于我们需要组成的排列尽可能的小，很容易知道3开头的排列已经是
        最大的了，所以我们把3和第一个大于等于3的元素交换位置即可得到【4,5,3,1】，
        正常情况下我们对4后面的元素从小到大即可得到4开头的最小的排列，不过我们发现这个算法中
        只要把4后面的元素逆序即可
        
    */
    public void nextPermutation(int[] nums) {
        // 1、找第一个index使得nums[index:]不是最大排列
        int index = nums.length-2;
        while( index>=0 && nums[index]>=nums[index+1])
            index--;
        if( index>=0 ){
            // 2、找到第一个nums[i]>nums[index]的数
            int index2 = nums.length-1;
            while( nums[index2]<=nums[index] )
                index2--;
            // 3、交换nums[index],nums[index2]
            int tmp = nums[index];
            nums[index] = nums[index2];
            nums[index2] = tmp;
        }
        // 4、逆序nums[index+1:]
        int l = index+1;
        int r = nums.length-1;
        while( l<r ){
            int tmp = nums[l];
            nums[l] = nums[r];
            nums[r] = tmp;
            l++;
            r--;
        }
    }
}